package com.peng.leetcode.swordoffer;

/**
 * Sword11Exist
 * 剑指 Offer 12. 矩阵中的路径
 * https://leetcode.cn/problems/ju-zhen-zhong-de-lu-jing-lcof/
 *
 * @author: lupeng6
 * @create: 2023/3/10 12:18
 */
public class Sword11Exist {

    private int[][] operations = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    private boolean[][] visited;


    public boolean exist(char[][] board, String word) {
        this.visited = new boolean[board.length][board[0].length];

        boolean flag = false;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                flag = flag || backtrack(board, word, i, j, 0);
            }
        }
        return flag;
    }

    private boolean backtrack(char[][] board, String word, int i, int j, int index) {
        if (index == word.length() - 1 && word.charAt(index) == board[i][j]) {
            return true;
        }
        if (board[i][j] != word.charAt(index)) {
            return false;
        }
        visited[i][j] = true;
        boolean ans = false;
        for (int[] operation : operations) {
            int i1 = i + operation[0];
            int j1 = j + operation[1];
            if (0 <= i1 && i1 < board.length && 0 <= j1 && j1 < board[i1].length && !visited[i1][j1]) {
                ans = ans || backtrack(board, word, i1, j1, index + 1);
            }
        }
        visited[i][j] = false;
        return ans;
    }
}
